package climbstair746

// https://leetcode-cn.com/problems/min-cost-climbing-stairs/
// 思路：
// 动态规划实现：
// 1. 定义状态：dp[i]表示从第i级台阶跳往下一级台阶的最小花费
// 2. 状态转移方程：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
// 3. 初始状态：dp[0] = cost[0], dp[1] = cost[1]
// 4. 返回值：min(dp[n-1], dp[n])
// 复杂度：O(n)
// 空间复杂度：O(n)
// 5. 优化空间复杂度：
// 1. 定义状态：a表示从第i-1级台阶跳往下一级台阶的最小花费，b表示从第i级台阶跳往下一级台阶的最小花费
// 2. 状态转移方程：a, b = b, min(a, b) + cost[i]
// 3. 初始状态：a = cost[0], b = cost[1]
// 4. 返回值：min(a, b)
// 复杂度：O(n)
// 空间复杂度：O(1)
func minCostClimbingStairs(cost []int) int {
	if len(cost) == 0 {
		return 0
	}
	if len(cost) == 1 {
		return cost[0]
	}
	if len(cost) == 2 {
		return min(cost[0], cost[1])
	}
	a, b := cost[0], cost[1]
	for i := 2; i < len(cost); i++ {
		a, b = b, min(a, b)+cost[i]
	}
	return min(a, b)
}
